package leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 基本计算器（双栈）
 */
public class BasicCalculatorNew {
    public static int calculator(String s) {
        // 分析：寻找右括号，只有加减不同考虑优先级的问题
        Deque<Integer> deque1 = new ArrayDeque<>(); // 存储数字
        Deque<Character> deque2 = new ArrayDeque<>(); // 存储符号
        List<Character> list = new ArrayList<>();
        // 遍历字符串，将其中有效字符按顺序存储在list中
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!isSpace(c)) {
                // 去掉其中全部空格
                list.add(c);
            }
        }
        // 如果表达式第一个字符是‘-’号，则在前面添加0，随后计算中不用考虑最前面的负号
        if (list.get(0) == '-') {
            list.add(0, '0');
        }
        // 遍历list对其中字符选择性处理，将所有减号与后方数字合起来作为负数存储只计算加运算
        /* 负号分为两种 1 前面是数字(-)  处理方法：再将负号弹出后需再加上+
                      2 前面是（ (#)  处理方法：弹出后无需加+
        */
        for (int i = 0; i < list.size(); i++) {
            char c = list.get(i);
            if (isNumber(c)) {
                // 是数字
                // 取全该数字
                int num = Character.getNumericValue(c);
                while (i + 1 < list.size() && isNumber(list.get(i + 1))) {
                    num = num * 10 + Character.getNumericValue(list.get(++ i));
                }
                // 判断其前面的符号是否为‘-’，若是则变为负数存储
                if (!deque2.isEmpty()) {
                    if (deque2.peek() == '-') {
                        // 1 这个负号前是数字
                        num = - num;
                        deque2.pop(); // 将负号弹出
                        // 需要再为deque2中添加+号
                        deque2.push('+');
                    } else if (deque2.peek() == '#') {
                        // 2 这个负号前是(
                        num = - num;
                        deque2.pop(); // 将负号弹出
                    }
                }
                deque1.push(num);
            } else {
                if (c == ')') {
                    // 是右括号，需要计算与其最近的括号之间的值
                    while (deque2.peek() != '(') {
                        int num2 = deque1.pop();
                        int num1 = deque1.pop();
                        deque1.push(num1 + num2);
                        deque2.pop();
                    }
                    deque2.pop();
                    // 判断（ 之前是否为负号若为负号重新存储为相反数
                    if (!deque2.isEmpty()) {
                        if (deque2.peek() == '-' || deque2.peek() == '#') {
                            deque1.push(- deque1.pop());
                            char tmp = deque2.pop();
                            if (tmp == '-') {
                                deque2.push('+');
                            }
                        }
                    }
                } else {
                    // 如果是负号，判断它的前一个是不是数字，若不是用#代替
                    if (c == '-' && i > 0 && list.get(i - 1) == '(') {
                        c = '#';
                    }
                    // 其余符号存入符号栈
                    deque2.push(c);
                }
            }
        }
        // 遍历结束，栈2还不为空，还需计算所有和
        while (!deque2.isEmpty()) {
            int num2 = deque1.pop();
            int num1 = deque1.pop();
            deque1.push(num1 + num2);
            deque2.pop();
        }
        // 若此时deque1还为空说明输入空返回0
        if (deque1.isEmpty()) {
            return 0;
        }
        return deque1.peek();
    }
    private static boolean isNumber(char c) {
        return Character.isDigit(c) ? true : false;
    }

    private static boolean isSpace(char c) {
        return Character.isSpaceChar(c) ? true : false;
    }
    public static void main(String[] args) {
        String s =  "(1+(4+5+2)-3)+(6+8)";
        System.out.println(calculator(s));
    }
}
